#include <stdio.h>
#include <stdlib.h>

// 定义二叉树的节点结构
typedef int ElemType;  // 元素类型，假设为整型

typedef struct BiTNode
{
    ElemType data;  // 数据域
    struct BiTNode *lchild, *rchild;  // 左右孩子指针
} BiTNode, *BiTree;

// 定义状态类型
typedef enum { ERROR, OK } Status;

// 创建新节点的函数
BiTree CreateNode(ElemType data)
{
    BiTree newNode = (BiTree)malloc(sizeof(BiTNode));
    if (newNode == NULL)
    {
        printf("内存分配失败\n");
        exit(-1);
    }
    newNode->data = data;
    newNode->lchild = newNode->rchild = NULL;
    return newNode;
}

// 从键盘输入创建二叉树的函数
BiTree CreateBiTree()
{
    ElemType data;
    scanf("%d", &data);

    if (data == -1)  // 使用-1表示空节点
    {
        return NULL;
    }

    BiTree newNode = CreateNode(data);
    printf("请输入 %d 的左子树: ", data);
    newNode->lchild = CreateBiTree();
    printf("请输入 %d 的右子树: ", data);
    newNode->rchild = CreateBiTree();

    return newNode;
}

// 中序遍历二叉树的递归函数
Status InOrderTraverse(BiTree T, Status(*Visit)(ElemType))
{
    if (T)
    {
        if (InOrderTraverse(T->lchild, Visit))  // 递归中序遍历左子树
        {
            if (Visit(T->data))  // 访问根节点
            {
                if (InOrderTraverse(T->rchild, Visit))  // 递归中序遍历右子树
                {
                    return OK;
                }
            }
        }
        return ERROR;
    }
    else
    {
        return OK;
    }
}

// 访问节点的简单函数，用于打印节点数据
Status PrintElement(ElemType e)
{
    printf("%d ", e);
    return OK;
}

// 主函数，用于测试中序遍历
int main()
{
    BiTree root;

    printf("请输入根节点的数据 (-1 表示空节点): ");
    root = CreateBiTree();

    // 中序遍历并打印二叉树
    printf("中序遍历结果: ");
    InOrderTraverse(root, PrintElement);
    printf("\n");

    return 0;
}